package leetcode_700;

import java.util.HashMap;
import java.util.Map;

/**
 *@author 周杨
 *SplitArrayIntoConsecutiveSubsequences_659  判断一个数组元素能否被拆分成几个连续子数组
 *describe:用贪心算法  每次优先形成3个元素的队列 如果有新的元素添加进来 判断添加进来的元素能否拆成3个元素的队列 AC 52%
 *2018年9月28日 下午1:12:19
 */
public class SplitArrayIntoConsecutiveSubsequences_659 {
	public boolean isPossible(int[] nums) {

		Map<Integer, Integer> unused_freq = new HashMap<Integer, Integer>(),
				need_freq = new HashMap<Integer, Integer>();
		for (int i : nums)//统计这个数字出现的总次数
			unused_freq.put(i, unused_freq.containsKey(i) ? 1 + unused_freq.get(i) : 1);

		for (int i : nums) {
			if (unused_freq.get(i) == 0)
				continue; // 这个数用完了

			if (need_freq.containsKey(i) && need_freq.get(i) > 0) {
				// 加到已经有的队列
				need_freq.put(i, need_freq.get(i) - 1);
				need_freq.put(i + 1, need_freq.containsKey(i + 1) ? need_freq.get(i + 1) + 1 : 1);
				unused_freq.put(i, unused_freq.get(i) - 1);
			} else if (unused_freq.containsKey(i + 1) && unused_freq.get(i + 1) > 0 && unused_freq.containsKey(i + 2)
					&& unused_freq.get(i + 2) > 0) {
				// 加到新的队列
				need_freq.put(i + 3, need_freq.containsKey(i + 3) ? 1 + need_freq.get(i + 3) : 1);
				unused_freq.put(i, unused_freq.get(i) - 1);
				unused_freq.put(i + 1, unused_freq.get(i + 1) - 1);
				unused_freq.put(i + 2, unused_freq.get(i + 2) - 1);
			} else {
				// 这个数无处容身
				return false;
			}
		}

		return true;
	}

}
